#include <limits.h>  // INT_MIN,INT_MAX
#include <math.h>    // abs,pow

#include <algorithm>      // sort
#include <iostream>       // cout,cin
#include <numeric>        // accumulate
#include <string>         // string
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <vector>         // vector

using namespace std;
// 链表结点的数据结构
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 如果x是2的幂则返回True，否则返回False
bool IsPowerOf2(int x) { return (x & (x - 1)) == 0; }

class Solution {
   public:
    ListNode *detectCycle(ListNode *head) {
        // 处理空链表的情况
        if (head == nullptr) {
            return nullptr;
        }

        // 寻找快慢针交点，判断是否有环
        ListNode *node1 = head, *node2 = head;
        do {
            if (node1->next == nullptr || node1->next->next == nullptr) {
                return nullptr;
            }
            node1 = node1->next->next;
            node2 = node2->next;
        } while (node1 != node2);

        // 寻找入环结点
        ListNode *node3 = head;
        while (node1 != node3) {
            node1 = node1->next;
            node3 = node3->next;
        }

        return node3;
    }
};

int main() {
    Solution solution;
    return 0;
}